class Heap {
  constructor(limit) {
    this.heap = Array(limit)
    this.limit = limit
    this.heapSize = 0
  }

  isEmpty() {
    return this.heapSize === 0
  }

  isFull() {
    return this.heapSize === this.limit
  }

  push(value) {
    if (this.isFull()) {
      throw Error('heap is full')
    }
    this.heap[this.heapSize] = value
    //
    this._heapInsert(this.heap, this.heapSize++)
  }


  pop() {
    let ans = this.heap[0]
    swap(this.heap, 0, --this.heapSize)
    this._heapify(this.heap, 0, this.heapSize)
    return ans
  }

  // 新加进来的数，现在停在了index位置，请依次往上移动
  // 移动到0位置， 或者干不掉自己的父节点了， 就停
  _heapInsert(arr, index) {
    while (arr[index] > arr[(index-1)/2]) {
      swap(arr, index, (index-1)/2)
      index = (index-1) / 2
    }
  }

  // 从index位置，往下看， 不断的下沉
  // 停： 较大的孩子都不在比index位置的数大， 说明已经没有孩子了
  _heapify(arr, index, heapSize) {
    let left = index * 2 + 1; // 左孩子
    while (left < heapSize) {
      let largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left
      largest = arr[largest] > arr[index] ? largest : index
      if (largest == index) {
        break
      }
      // index 和 较大孩子， 要互换
      swap(arr, largest, index)
      index = largest
      left = index * 2 + 1
    }
  }
}


function swap(arr,a,b) {
  let tmp = arr[a]
  arr[a] = arr[b]
  arr[b] = tmp
}


let h = new Heap(5)
h.push(3)
h.push(2)
h.push(1)
h.push(5)
h.push(4)

console.log(h.pop())
console.log(h.pop())
console.log(h.pop())
console.log(h.pop())
console.log(h.pop())